#include <stdio.h>
binarySearch(int a[], int n, int key){
	//arrat：数组 ， low:上界；  high:下界;  key:查找的数据
    int low = 0;//初始化查找区间 
    int high = n - 1;
    //一直遍历取中间 
    while(low<= high){
        int mid = (low + high)/2;
        int midVal = a[mid];//将MID的值储存起来 
        if(midVal<key)
            low = mid + 1;//移动LOW的下标 ,中心节点关键字偏小，查找高半段
        else if(midVal>key)
            high = mid - 1;//移动hight的下标 ,中心节点关键字偏大，查找低半段 
        else
            return mid;
    }
    return -1;
}
int main(){
    int i, val, ret;
    int a[8]={-32, 12, 16, 24, 36, 45, 59, 98};
    for(i=0; i<8; i++)
        printf("%d\t", a[i]);
    printf("\n请输人所要查找的元素：");
    scanf("%d",&val);
    ret = binarySearch(a,8,val);//调用方法 
    if(-1 == ret)
        printf("查找失败 \n");
    else
        printf ("查找成功 \n");
    return 0;
}
// 二分查找分析：
// 二分查找每次排除掉一半的不适合值，所以对于N个元素的情况：
// 一次二分剩下：N/2
// 两次二分剩下：N/2/2 = n/4
// 三次二分查找剩下：N/2/2/2 = N/8
// .....
// M次二分剩下：n / (2^M)
 
// 在最坏情况下是在排除到只剩下最后一个值之后得到结果，即
// 2^m = N
// 推出时间复杂度是以2为底的对数：
// O(N)= log2(N)